"""
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
"""
import time

start = time.time()
time.sleep(1)
s = "babad"
# s = "cbbd"
sf1 = ""  # 存储中间变量
sf2 = ""  # 存储最终结果
i = 0     # 控制循环
sc = 0
while i < len(s):
    sf1 += s[i]        # 先给sf1赋值
    if sf1[::-1] == sf1:   # 判断正序和反序是否一致
        i += 1
        if len(sf1) > len(sf2):  # 找到字符串s中最长的
            sf2 = sf1
    else:
        if len(sf1) == (len(s)-sc):  # 判断是否取到s的最后一个字符
            sf1 = ""    # 清空中间变量 以便下次循环使用
            i = sc
            sc += 1
        i += 1

print(sf2)
end = time.time()
print(f"运行时间:{end - start}")
